#include <vector>
#include <queue>

using std::vector;
using std::queue;
using std::pair;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        queue<pair<int, int>> q;
        int m = grid.size();
        int n = grid[0].size();
        int ret = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    ret++;
                    grid[i][j] = '0';
                    q.emplace(i, j);
                    while (!q.empty()) {
                        int a = q.front().first;
                        int b = q.front().second;
                        q.pop();
                        if (a > 0 && grid[a - 1][b] == '1') {
                            grid[a - 1][b] = '0';
                            q.emplace(a - 1, b);
                        }
                        if (a < m - 1 && grid[a + 1][b] == '1') {
                            grid[a + 1][b] = '0';
                            q.emplace(a + 1, b);
                        }
                        if (b > 0 && grid[a][b - 1] == '1') {
                            grid[a][b - 1] = '0';
                            q.emplace(a, b - 1);
                        }
                        if (b < n - 1 && grid[a][b + 1] == '1') {
                            grid[a][b + 1] = '0';
                            q.emplace(a, b + 1);
                        }
                    }
                }
            }
        }
        return ret;
    }
};